package 日常作业;
// 数组定义与使用中的 数组练习题

//1.  数组转字符串
/**
 * 模拟实现 Arrays.toString方法的功能
 * 把一个数组转换成 字符串 并返回
 */
//import java.util.Arrays;
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5};
//        String sc = Arrays.toString(arr);
//        System.out.println(sc);//[1, 2, 3, 4, 5]
//        System.out.println();
//        String sc2 = MY_toString(arr);
//        System.out.println(sc2);
//    }
//
//    private static String MY_toString(int[] arr) {
//
//        String sc = "[";
//        for (int i = 0; i < arr.length; i++) {
//
//            sc += arr[i];
//            if(i != arr.length - 1)
//                sc += ", ";
//        }
//        sc += "]";
//        return sc;
//    }
//}

//2. 数组拷贝
/**
 * 模拟实现 Arrasy.copyOf
 * 深层次拷贝数组中每一个元素，并返回。
 */
//import java.util.Arrays;
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5};
//        int[] cop1 = Arrays.copyOf(arr, arr.length);
//        System.out.println(Arrays.toString(cop1));
//        System.out.println("------对比--------");
//        int[] cop2 = MY_copyOf(arr, arr.length);
//        System.out.println(Arrays.toString(cop2));
//    }
//
//    private static int[] MY_copyOf(int[] arr, int length) {
//
//        int[] str = new int[length];
//        for (int i = 0; i < length; i++) {
//            str[i] = arr[i];
//        }
//        return str;
//    }
//}

//3. 找数组中的最大元素.
/**
 * 给定一个整型数组,
 * 找到其中的最大元素 (找最小元素同理)
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,6,9,5};
//        System.out.println(max(arr));
//    }
//
//    public static int max(int[] arr){
//
//        int max = arr[0];
//        for (int i = 0; i < arr.length; i++) {
//
//            if(max < arr[i])
//                max = arr[i];
//        }
//        return max;
//    }
//}

//4 求数组中元素的平均值
/**
 * 求数组里面所有元素的返回值
 * 返回类型是 double 浮点数
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5};
//        System.out.println(average(arr));
//    }
//
//    public static double average(int[] arr){
//
//        int sum = 0;
//        for (int i = 0; i < arr.length; i++) {
//
//                sum += arr[i];
//        }
//        return (double)sum / (double)arr.length;
//    }
//}

//5 查找数组中指定元素(顺序查找)

/**
 * 给定一个数组, 再给定一个元素,
 * 找出该元素在数组中的位置,并返回其下标.
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5};
//        int rep = find(arr, 8);
//        if(rep == -1){
//            System.out.println("不存在该元素");
//        }else{
//            System.out.println(arr[rep] + " 的下标为" + rep);
//        }
//    }
//    public static int find(int[] arr, int x){
//
//        for (int i = 0; i < arr.length; i++) {
//
//            if(arr[i] == x)
//                return i;
//        }
//        return -1;
//    }
//}

//6 查找数组中指定元素(二分查找)  用递归方法 和 非递归方法写
/**
 *  针对有序数组, 可以使用更高效的二分查找
 *  有序分为 "升序" 和 "降序"
 * 如 1 2 3 4 , 依次递增即为升序.
 * 如 4 3 2 1 , 依次递减即为降序.
 * 以升序数组为例, 二分查找的思路是先取中间位置的元素,
 * 看要找的值比中间元素大还是小. 如果小, 就去左边找;
 * 否则就去右边找.
 */

//非递归方法写
//public class Test_4_10_ZY {
//    public static int conut = 0;
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
//        int num = 10;
//        int rep = toFind(arr, num);
//        System.out.println(conut);
//        if(rep == -1){
//            System.out.println("不存在该元素");
//        }else{
//            System.out.println(num + " 的下标为 " + rep);
//        }
//    }
//    public static int toFind(int[] arr, int rep){
//
//        int left = 0;
//        int right = arr.length - 1;
//        int middle = (left + right) / 2;
//        while(left <= right){
//            conut++;
//            if(rep < arr[middle]){
//                right = middle - 1;
//            }else if(rep > arr[middle]){
//                left = middle + 1;
//            }else{
//                return middle;
//            }
//            middle = (left + right) / 2;
//        }
//        return -1;
//    }
//}

//用递归方法
//public class Test_4_10_ZY {
//    public static int conut = 0;
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
//        int num = 10;
//        //用递归方法需要多输入两个参数：左边的下标 和 右边的下标（范围）
//        int rep = toFind(arr, num, 0, arr.length - 1);
//        System.out.println(conut);
//        if(rep == -1){
//            System.out.println("不存在该元素");
//        }else{
//            System.out.println(num + " 的下标为 " + rep);
//        }
//    }
//    public static int toFind(int[] arr, int rep, int left, int right){
//
//        conut++;
//        int middle = (left + right) / 2;
//
//        if(left <= right){
//        //必须是 <= 不然边界值找不到
//
//           if(arr[middle] == rep){
//               return middle;
//           }else if(rep < arr[middle]){
//
//               return toFind(arr, rep, left, middle - 1);
//           }else if(rep > arr[middle]){
//
//               return toFind(arr, rep, middle + 1,  right);
//           }
//       }
//
//        return -1;
//    }
//}

//7 检查数组的有序性
/**
 * 给定一个整型数组, 判断是否该数组是有序的(升序)(降序)
 * 有序返回： true 无序返回：false
 */
//public class Test_4_10_ZY {
//    public static int conut = 0;
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
//        int[] arr1 = new int[]{9,8,7,6,5};
//        int[] arr2 = new int[]{9,8,4,6,5};
//        System.out.println("是否是有序：" + Orderly(arr));
//        System.out.println("是否是有序：" + Orderly(arr1));
//        System.out.println("是否是有序：" + Orderly(arr2));
//
//
//    }
//    //判断是否升序
//    public static boolean Orderly(int[] arr){
//
//        if(arr.length <= 1)
//            return false;
//        if(arr[0] < arr[1]) {
//            //判断是否升序
//            for (int i = 0; i < arr.length - 1; i++) {
//                if (arr[i] > arr[i + 1])
//                    return false;
//            }
//        }else if(arr[0] > arr[1]){
//            //判断是否降序
//            for (int i = 0; i < arr.length - 1; i++) {
//                if(arr[i] < arr[i + 1])
//                    return false;
//            }
//        }else{
//            return false;
//        }
//
//        return true;
//    }
//
//}

//8 数组排序(冒泡排序)
/**
 * 功能：给定一个数组, 让数组升序 (降序) 排序
 * 算法思路：
 * 每次尝试找到当前待排序区间中最小(或最大)的元素, 放到数组最前面(或最后面)
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{5,3,4,6,7,1,0,8,2};
//        sort(arr);
//        for (int x :
//                arr) {
//            System.out.print(x + " ");
//        }
//    }
//    public static void sort(int[] arr){
//
//        int input = 0;
//        for (int i = 0; i <arr.length; i++) {
//
//            input = i;
//            for (int j = i; j < arr.length; j++) {
//
//                if(arr[input] > arr[j])
//                    input = j;
//            }
//            int tmp = arr[i];
//            arr[i] = arr[input];
//            arr[input] = tmp;
//        }
//    }
//}

//9 数组逆序
/**
 * 给定一个数组, 将里面的元素逆序排列.
 * 思路:
 * 设定两个下标, 分别指向第一个元素和最后一个元素. 交换两个位置的元素.
 * 然后让前一个下标自增, 后一个下标自减, 循环继续即可.
 */
//import java.util.Arrays;
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
//        System.out.println("---逆序之前---");
//        System.out.println(Arrays.toString(arr));
//        Reverse(arr);
//        System.out.println("---逆序之后---");
//        System.out.println(Arrays.toString(arr));
//
//    }
//    public static void Reverse(int[] arr){
//
//        int left = 0;
//        int right = arr.length - 1;
//        while(left < right){
//
//            int tmp = arr[left];
//            arr[left] = arr[right];
//            arr[right] = tmp;
//            left++;
//            right--;
//        }
//    }
//}

//10 数组数字排列
/**
 * 要求：给定一个整型数组,
 * 将所有的偶数放在前半部分,
 * 将所有的奇数放在数组后半部分
 * 方法1：用冒泡法查找，把遇到的偶数排到最前面，以此类推。
 * 方法2：设定两个下标分别指向第一个元素和最后一个元素.
 * 用前一个下标从左往右找到第一个奇数, 用后一个下标从右往左找到第一个偶数, 然后交换两个位置的元素.
 */
//方法1： 效率慢
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{5,3,4,6,7,1,0,8,2};
//        sort(arr);
//        for (int x :
//                arr) {
//            System.out.print(x + " ");
//        }
//    }
//    public static void sort(int[] arr){
//
//        int input = 0;
//        for (int i = 0; i <arr.length; i++) {
//
//            input = i;
//            for (int j = i; j < arr.length; j++) {
//
//                if(arr[j] % 2 == 0) {
//                    input = j;
//                    break;
//                }
//            }
//            int tmp = arr[i];
//            arr[i] = arr[input];
//            arr[input] = tmp;
//        }
//    }
//}

//方法2 ： 效率就快很多
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{5,3,4,6,7,1,0,8,2};
//        sort(arr);
//        for (int x :
//                arr) {
//            System.out.print(x + " ");
//        }
//    }
//    public static void sort(int[] arr){
//
//       int left = 0;
//       int right = arr.length - 1;
//
//       while(left < right){
//
//           //找到左边的奇数
//           while(arr[left] % 2 == 0 && left < right){
//               left++;
//           }//注释：条件必须是可执行条件，而不是终止条件
//           //找到右边的偶数
//           while(arr[right] % 2 != 0 && right > left){
//               right--;
//           }
//           int tmp = arr[left];
//           arr[left] = arr[right];
//           arr[right] = tmp;
//       }
//    }
//}

// 11 两数之和
/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 * 示例 1：
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{2,7,11,4,15,5};
//        int target = 9;
//        String sc = Add(arr, target);
//        System.out.println(sc);
//    }
//    public static String Add(int[] arr, int rep){
//
//        String sc = "[";
//        for (int i = 0; i < arr.length - 1; i++) {
//
//            for (int j = i + 1; j < arr.length; j++) {
//
//                    if(arr[i] + arr[j] == rep){
//                        sc += i + ", " + j;
//                        if(j != arr.length - 1)
//                            sc += ", ";
//                    }
//
//            }
//
//        }
//        sc += "]";
//        return sc;
//    }
//}

//12 只出现一次的数字 用异或的特性
/**
 * 给定一个非空整数数组，除了某个元素只出现一次以外，
 * 其余每个元素均出现两次。找出那个只出现了一次的元素。
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args){
//
//        int[] arr = new int[]{1,2,3,4,3,2,1};
//        int rep = only(arr);
//        System.out.println(rep);
//    }
//    public static int only(int[] arr){
//
//        int rep = arr[0];
//        for (int i = 1; i < arr.length; i++) {
//
//            rep ^= arr[i];
//        }
//        return rep;
//    }
//}

//13 多数元素

import java.util.Arrays;

/**
 * 给定一个大小为 n 的数组，找到其中的多数元素。
 * 多数元素是指在数组中出现次数 大于  n/2 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */
// 方法1 用快速排序来解决 （最优的）
//import java.util.Arrays;
//public class Test_4_10_ZY {
//    public static void main(String[] args){
//
//        int[] arr = new int[]{1,2,3,3,4,3,3};
//        System.out.println(Arrays.toString(arr));
//        // 因为题目给的是 必定存在 多数元素
//        //所以在排序后，中间的值必定是 多数元素
//        //因为它存在的数量 大于 n / 2
//        Arrays.sort(arr);
//        System.out.println("输出：" + arr[arr.length / 2]);
//    }
//
//}
// 方法2 摩尔投票法–>消消乐(还不理解)

//14 所以元素的和
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = new int[]{1,2,3,3,4,3,3};
//        System.out.println(Arrays.toString(arr));
//        int sum = Sum(arr);
//        System.out.println("所以元素的和 = " + sum);
//    }
//
//    private static int Sum(int[] arr) {
//
//        int sum = 0;
//        for (int x :
//                arr) {
//            sum += x;
//        }
//        return sum;
//    }
//}

//15 存在连续三个奇数的数组
/**
 * 给你一个整数数组 arr，请你判断数组中是否存在连续
 * 三个元素都是奇数的情况：如果存在，
 * 请返回 true ；否则，返回 false 。
 */
//public class Test_4_10_ZY {
//    public static void main(String[] args) {
//
//        int[] arr = {1,2,34,3,4,5,7,23,12};
//        System.out.println(three_Odd(arr));
//    }
//    public static boolean three_Odd(int[] arr){
//
//        int conut = 0;
//        for (int i = 0; i < arr.length - 2; i++) {
//
//           if(arr[i] % 2 != 0){
//               if(arr[i + 1] % 2 != 0){
//                   if(arr[i + 2] % 2 != 0){
//                       return true;
//                   }
//               }
//           }
//
//        }
//
//        return false;
//    }
//}